#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEBUG
///////////////////////////////////////////////////////////
//Graph
//#define INFINITY INT_MAX //无穷
#define INFINITY 10000 //无穷

#define MAX_VERTEX_NUM 100   //顶点的最大个数
#define VRType int          //表示顶点之间的关系的变量类型
#define InfoType char       //存储弧或者边额外信息的指针变量类型
#define VertexType int		//图中顶点的数据类型

//枚举图的 4 种类型
//带权的图称为网
typedef enum{
	DG = 0, //有向图， Digraph
	DN, //有向网，Digraph Network
	UDG, //无向图，UnDigraph
	UDN //无向网, UnDigraph Network
}GraphKind;

typedef struct {
	//对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值
    VRType adj; //Adjacent,邻近的，邻接
    InfoType * info; //弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//V: Vertex,顶点
//R: Arc, 弧，有方向的叫做弧，有向图
//无向图：Edge, 边
//无向图：UDG，n个顶点，则最多有 n(n-1)/2条边
//如果无向图有n(n-1)/2条边，则称为完全图
//边的数量e < nlogn，稀疏图, Sparse graph
//反之成为稠密图, Dense graph
//权：Weight，图的边或弧，具有相关的数，比如长度，叫做权
//1-based
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM + 1];        //存储图中顶点数据
	//二维数组，记录顶点之间的关系
    ArcCell arcs[MAX_VERTEX_NUM + 1][MAX_VERTEX_NUM + 1];
	int vexnum; //图的顶点数
	int arcnum; //图的弧（边）数
    GraphKind kind; //记录图的种类
}MGraph;

///////////////////////////////////////////////////////////
//queue
#define QUEUE_SIZE 100

struct queue{
	int front;
	int rear;
	unsigned int len;
};

//return 1 if empty
int queueEmpty(struct queue* q)
{
	if(q->front == (q->rear % q->len)) {
        return 1;
    }
	return 0;
}

//return 1 if full
int queueFull(struct queue* q)
{
	if (((q->rear + 1) % q->len) == q->front) {
		return 1;
	}
	return 0;
}


//return rear index
//rear point to next empty room
int enQueue(VertexType *ary, struct queue* q, VertexType data)
{
	if (queueFull(q)) {
		printf("queue is full");
		return q->rear;
	}

	ary[q->rear] = data;
	q->rear = (q->rear + 1) % q->len;
    return q->rear;
}

//front point to queue head
//返回队列头元素的值
VertexType deQueue(VertexType *ary, struct queue* q)
{
	VertexType ret = ary[q->front];
    if(queueEmpty(q)) {
        printf("queue is empty");
        return ret;
    }
    q->front = (q->front + 1) % q->len;
    return ret;
}

void initQueue(struct queue* q, unsigned int maxLen)
{
	q->front = 0;
	q->rear = 0;
	q->len = maxLen;
}

void destroyQueue(struct queue* q)
{
	initQueue(q, 0);
}


///////////////////////////////////////////////////////////
//stack

#define STACK_INIT_SIZE 100
typedef struct aryStack{
	VertexType*top;  //stack top
	VertexType*base; //init NULL
	int stacksize; //size count by SELemType
}SqStack;

int InitStack(SqStack *s)
{
	s->base = (VertexType*)malloc(STACK_INIT_SIZE * sizeof(VertexType));
	if (!s->base)
		return -1;
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return 0;
}

int DestroyStack(SqStack *s)
{
	if(s->base)
		free(s->base);
	return 0;
}

//if stack is NULL,
//return 1 if NULL; else return 0
int StackEmpty(SqStack *s)
{
	if (s->top == s->base)
		return 1;
	return 0;
}

int Push(SqStack *s, VertexType e)
{
	if(s->top - s->base >= s->stacksize) {
		printf("stack overflow \n");
		return -1;
	}
	*s->top = e;
	s->top++;
	return 0;
}

int GetTop(SqStack *s, VertexType* e)
{
	if(StackEmpty(s))
		return -1;
	*e = *(s->top - 1);
	return 0;
}

VertexType GetTopVal(SqStack *s)
{
	VertexType val;
	GetTop(s, &val);
	return val;
}


int Pop(SqStack *s, VertexType *e)
{
	if(StackEmpty(s))
		return -1;
	s->top--;
	*e = *(s->top);
	return 0;
}

///////////////////////////////////////////////////////////
//graph algorithm


//矩阵对称
VRType Adjacent_matrix_test[6][6] = {
	{0, 1, 4, 10000, 10000, 10000},
	{1, 0, 2, 7, 5, 10000},
	{4, 2, 0, 10000, 1, 10000},
	{10000, 7, 10000, 0, 3, 2},
	{10000, 5, 1, 3, 0, 6},
	{10000, 10000, 10000, 2, 6, 0}
};

void CreateUDN(MGraph* G, int vernum, int matrix_num, VRType* ary)
{
	int i, j;
	int arcnum = 0;

	memset(G, INFINITY, sizeof(MGraph));
	G->kind = UDN;
	G->vexnum = vernum;
    for (i = 1; i <= vernum; i++) {
		G->vexs[i] = i; //1-based index
		for (j = 1; j <= vernum; j++) {
			G->arcs[i][j].adj = ary[(i-1) * matrix_num + j-1];
			if (G->arcs[i][j].adj != INFINITY) {
				if (i == j) //skip diagonal
					continue;
				arcnum++;
			}
		}
    }
	G->arcnum = arcnum / 2;
#ifdef DEBUG
	printf("vernum=%d, arcnum=%d\n", G->vexnum, G->arcnum);
#endif
}

void PrintGraph(MGraph *G)
{
	int i, j;
    for (i = 1; i <= G->vexnum; i++) {
        for (j = 1; j <= G->vexnum; j++) {
            printf("%d ", G->arcs[i][j].adj);
        }
		printf("\n");
    }
}

void Print2DArray(char* name, int n, int* ary)
{
	int i, j;

	if (name)
		printf("%s\n", name);

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			printf("%d ", ary[i * n + j]);
		}
		printf("\n");
	}
	printf("\n");
}

void print_dis(MGraph* G, int* dist)
{
	int i;

	//printf distance
	printf("vertex index:   ");
	for (i = 1; i <= G->vexnum; i++) {
		printf("%d ", i);
	}
	printf("\ndistance weight:");
	for (i = 1; i <= G->vexnum; i++) {
		printf("%d ", dist[i]);
	}
	printf("\n\n");
}

/* 打印从source顶点到dest顶点的路径
 * source顶点是固定的
 * dijkstra算法：计算从指定source到所有其他顶点的最短路径
 * */
void print_dijkstra_path(MGraph* G, int* path, int dest)
{
	int i, index;
	SqStack s;
	int lastIndex, weight;

	//printf path
	InitStack(&s);
	i = dest;
#ifdef DEBUG
	printf("vertex 1 to %d path:", i);
#endif
	index = path[i];
	if (!index) {
#ifdef DEBUG
		printf("1->1, weight=0\n");
#else
		printf("0\n");
#endif
		return;
	}

	lastIndex = i;
	weight = 0;
	while (index) {
		weight = weight + G->arcs[lastIndex][index].adj;
		Push(&s, index);
		lastIndex = index;
		index = path[index];
	}

	while (!StackEmpty(&s)) {
		Pop(&s, &index);
#ifdef DEBUG
		printf("%d->", index);
#else
		printf("%d\n", index - 1);
#endif
	}
#ifdef DEBUG
	printf("%d, weight=%d\n", i, weight);
#else
	printf("%d\n", i - 1);
#endif

	DestroyStack(&s);
}

void print_dijkstra_path_all(MGraph* G, int* path)
{
	int i;

	//printf path
	for (i = 1; i <= G->vexnum; i++) {
		print_dijkstra_path(G, path, i);
	}
}

VertexType node_ary[QUEUE_SIZE];
//0: not visited; 1: visited
//1-based
#define VISITED 1
#define NOT_VISITED (0)
int visited[MAX_VERTEX_NUM + 1];

// The output array. dist[i] will hold the shortest
// distance from src to i
int dist[MAX_VERTEX_NUM + 1]; //distance

//0: init to zero
int path[MAX_VERTEX_NUM + 1]; //record vertext path

/* BFS: Broadth First Search
 * 按照层次遍历图，类似于按照层次遍历树
void BFS(Vertex v)
{
	visited[v] = true
	enqueue(v, q)
	while(!isempty(q)) {
		v = dequeue(q)
		for (v的每个邻接点w）{
			if(!visited[w]) {
				visited[w] = true
				dist[w] = dist[v] + 1
				path[w] = v
				enqueue(w, q)
			}
		}
	}
}
*/

/* 在图G中，寻找顶点v的邻接点
 * 返回邻接点
 * 如果没有邻接点，返回0
 * */
VertexType get_adj_vertex(MGraph *G, VertexType v)
{
	int i, w;

	//find all adjacent vertex, skip INFINITY and diagonal
	for (i = 1, w = 1; i <= G->vexnum; i++, w++) {
		if ((G->arcs[v][i].adj != INFINITY) && (w != v))
			if (NOT_VISITED == visited[w]) {
				return w;
			}
	}

	return 0;
}

/* 相当于权值为1的最短路径算法 */
void BFSTraverse(MGraph *G)
{
	struct queue sq;
	VertexType v, w;

	initQueue(&sq, QUEUE_SIZE);
	memset(visited, NOT_VISITED, sizeof(visited));
	memset(dist, NOT_VISITED, sizeof(visited));
	memset(path, NOT_VISITED, sizeof(visited));

	//traverse, from node "1" start
	w = 1;
	visited[w] = VISITED;
	enQueue(node_ary, &sq, w);

	while (!queueEmpty(&sq)) {
		v = deQueue(node_ary, &sq);
		while(1) {
			w = get_adj_vertex(G, v);
			if (!w)
				break;
			visited[w] = VISITED;
			dist[w] = dist[v] + 1;
			path[w] = v;
			enQueue(node_ary, &sq, w);
		}
	}
#ifdef DEBUG
	printf("BFSTraverse result:\n");
	print_dis(G, dist);
	print_dijkstra_path_all(G, path);
#endif
	destroyQueue(&sq);
}

///////////////////////////////////////////////////////////
/*
 * 从顶点s开始，计算到有权图G所有顶点的最短路径
 * 结果房子path[]中
 * s: source, shortest path
 * dist[]：起始点到当前顶点权值的和
 * path[]: 起始点到当前顶点，经过的前一个顶点索引
 * visited[]: 当前节点是否被访问过
 *
 void Dijkstra(vertex s)
 {
	while(1) {
		v = 未收录顶点中权最小者
		if(这样的顶点不存在)
			break;
		visited[v] = true
		for (v的每个邻接点w) {
			if( visited[w] == false && 
				dist[v] + <v,w>的权值 < dist[w] ){
					dist[w] = dist[v] + <v,w>的权值
					path[w] = v
				}
			}//end if
		}//end for
	}//end while
 }
 * */

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int *dist, int *visit, int vexnum)
{
	// Initialize min value
	int min = INFINITY, min_index = INFINITY;
	int v;

	for (v = 1; v <= vexnum; v++) {
		if (visit[v] == NOT_VISITED && dist[v] <= min) {
			min = dist[v];
			min_index = v;
		}
	}

	return min_index;
}


void Dijkstra(MGraph *G, VertexType src)
{
	int v, i, w = 0;
	int weight;

	//init
	// Initialize all distances as INFINITE and path[] as false
	for (i = 1; i <= G->vexnum; i++) {
		dist[i] = INFINITY;
		visited[i] = NOT_VISITED;
		path[i] = 0;
	}
	// Distance of source vertex from itself is always 0
	dist[src] = 0;
	
	// Find shortest path for all vertices
	while (1) {
		//v = 未收录顶点中权最小者
		v = minDistance(dist, visited, G->vexnum);
		if (v == INFINITY) //reach to last vertex
			break;
		visited[v] = VISITED;
		//for (v的每个邻接点w) {
		//find all adjacent vertex, skip INFINITY and diagonal
		for (i = 1, w = 1; i <= G->vexnum; i++, w++) {
			if ((G->arcs[v][i].adj != INFINITY) && (w != v))
				if (NOT_VISITED == visited[w]) {
					weight = G->arcs[v][w].adj;
					if ((visited[w] == NOT_VISITED) &&
						(dist[v] + weight < dist[w])) {
						dist[w] = dist[v] + weight;
						path[w] = v;
					}
				}
		}//end for
	}

	//print result
#ifdef DEBUG
	printf("\n\nDijkstra result:\n");
	print_dis(G, dist);
	print_dijkstra_path_all(G, path);
#endif
}

#define DIRECT_PATH (-1)
/*
path
-1 -1 1 4 2 4
-1 -1 -1 4 2 4
1 -1 -1 4 -1 4
4 4 4 -1 -1 -1
2 2 -1 -1 -1 3
4 4 4 -1 3 -1

2 - 6
2-5 + 5-6
2-3 + 3-5 + 5-4 + 4-6
final:
	2-3-5-4-6
*/

void print_floyd_path(int* path, int n, VertexType src, VertexType dest, 
	struct queue* q, int* res_ary)
{
	int vertex;

	//1-5: 1-4 + 4-5
	vertex = path[src * n + dest]; //vertex = 4
	if (vertex == DIRECT_PATH) {
#ifdef DEBUG
		printf("->%d", dest + 1);
#else
		//printf("%d\n", dest);
		if (q && res_ary)
			enQueue(res_ary, q, dest);
#endif
		return;
	}

	print_floyd_path(path, n, src, vertex, q, res_ary);
	print_floyd_path(path, n, vertex, dest, q, res_ary);
}

enum print_type {
	PRINT_LENGTH = 0,
	PRINT_PATH
};

int get_floyd_dis(int n, int src, int dest, int* dis)
{
	int i, ret;
	i = (src - 1) * n + dest - 1;
	ret = dis[i];
#ifdef DEBUG
	printf("from %d to %d, shortest length is %d\n", src, dest, ret);
#endif
	return ret;
}


void floyd_shortpath_free(int* ret_D, int* ret_path)
{
	if (ret_D)
		free(ret_D);
	if (ret_path)
		free(ret_path);
}

/*
 * 在图G中，计算最短路径
 * */
void floyd_shortpath(MGraph *G, int** ret_D, int** ret_path)
{
	int N;
	int i, j, k;
	int *D;
	int *path;

	N = G->vexnum;
	D = malloc(N * N * sizeof(VRType));
	path = malloc(N * N * sizeof(int));

	//init
	for(i = 0; i < N; i++) {
		for(j = 0; j < N; j++) {
			D[i * N + j] = G->arcs[i+1][j+1].adj;
			path[i * N + j] = DIRECT_PATH;
		}
	}

	//search shortest path
	for( k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for( j = 0; j < N; j++) {
				//D[i][k] + D[k][j] < D[i][j]
				if(D[i*N+k] + D[k*N+j] < D[i*N+j]) {
					D[i*N+j] = D[i*N+k] + D[k*N+j];
					path[i*N+j] = k;
				}//end if
			}//end 3rd for
		}//end 2nd for
	}//end 1st for

#ifdef DEBUG
	Print2DArray("weight", N, D);
	Print2DArray("path", N, path);
#endif

	//free(path);
	//free(D);
	*ret_D = D;
	*ret_path = path;
}

///////////////////////////////////////////////////////////
//main 

MGraph testGraph;
VRType matrix_input[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

void get_user_input(VRType* ary, int num, int matrix_num)
{
	int i, j, index;
	for (i = 0; i < num; i++) {
		for (j = 0; j < num; j++) {
			index = i * matrix_num + j;
			scanf("%d", &ary[index]);
		}
	}
}

void print_34(int vexnum, int* dist)
{
	int i;
	printf("\n");
	for (i = 1; i <= vexnum; i++)
		printf("%d\n", dist[i]);
	printf("\n");
}

/*
 * 实验4.1，求复权图中的一个节点到所有节点的最短路径长度
 * 输入：
 *	先输入一个小于等于100的正整数n，这是赋权图的顶点数
 *	再输入这个图的邻接矩阵
 *	10000表示无穷大
 *输出：
	按照节点编号的顺序，输出0号节点到所有节点的最短路径的长度
例子：
input 
6
0 1 4 10000 10000 10000
1 0 2 7 5 10000
4 2 0 10000 1 10000
10000 7 10000 0 3 2
10000 5 1 3 0 6
10000 10000 10000 2 6  0
输出：
0 1 3 7 4 9
*/
void test_34(void)
{
	int vernum = 6;
	int matrix_num = vernum;
	VRType* ary;
#ifdef DEBUG
	ary = Adjacent_matrix_test[0];
#else
	matrix_num = MAX_VERTEX_NUM;
	scanf("%d", &vernum);
	ary = matrix_input[0];
	get_user_input(ary, vernum, matrix_num);
#endif

	CreateUDN(&testGraph, vernum, matrix_num, ary);
#ifdef DEBUG
	BFSTraverse(&testGraph);
#endif
	Dijkstra(&testGraph, 1);
	print_34(testGraph.vexnum, dist);
	//floyd_shortpath(&testGraph, 2, 6);
	//floyd_shortpath(&testGraph, 1, 6);
	//PrintGraph(&testGraph);
}

/* 4.2：用迪杰斯特拉算法求一点到其它所有节点的最短路径
 ** 输入：
 *	先输入一个小于等于100的正整数n，这是赋权图的顶点数
 *	再输入这个图的邻接矩阵
 *	10000表示无穷大
 *	最后输入两个整数表示2个点：0到n-1之间
 *
 *输出：
	先用迪杰斯特拉算法求给定的第一个点到其余所有节点的最短路径
	然后再输出给定两个点的最短路径
	按顺序输出最短路径上每一个点，每个数据占一行
 * */
/*
 * test data
 4
 0 2 10 10000
 2 0 7 3
 10 7 0 6
 10000 3 6 0
 0 2

output:
0
1
2
 * */
int ary_35[4][4] = {
	{0, 2, 10, 10000},
	{2, 0 ,7, 3},
	{10, 7, 0, 6},
	{10000, 3, 6, 0}
};

void test_35(void)
{
	int vernum = 4;
	int matrix_num = vernum;
	VRType* ary;
	int source, dest;

#ifdef DEBUG
	ary = ary_35[0];
	source = 1, dest = 3;
#else
	matrix_num = MAX_VERTEX_NUM;
	scanf("%d", &vernum);
	ary = matrix_input[0];
	get_user_input(ary, vernum, matrix_num);
	scanf("%d", &source);
	scanf("%d", &dest);
	source++; //0-based to 1-based
	dest++;
#endif

	CreateUDN(&testGraph, vernum, matrix_num, ary);
	Dijkstra(&testGraph, source);
	printf("\n");
	print_dijkstra_path(&testGraph, path, dest);
}



/* 4.3：用弗洛伊德算法求任意两点间的最短路径
 ** 输入：
 *	先输入一个小于等于100的正整数n，这是赋权图的顶点数
 *	再输入这个图的邻接矩阵
 *	10000表示无穷大
 *	之后再输入小于100的正整数m：m对顶点
 *	最后的m行输入顶点对：
 *	每一行：输入两个整数表示2个点：0到n-1之间
 *
 *输出：
	用弗洛伊德算法求任意两点间的最短路径的长度
	输出给定两个点的最短路径的长度
 * */
/*
 * test data
 4
 0 2 10 10000
 2 0 7 3
 10 7 0 6
 10000 3 6 0
 2
 0 2
 3 0

output:
9
5
 * */
//4-3和4-2的输入邻接矩阵相同，所以直接采用4-2的输入矩阵
void test_36_common(enum print_type type)
{
	int vernum = 4;
	int matrix_num = vernum;
	VRType* ary;
	int* ret_dis = NULL; //record distance
	int* ret_path = NULL; //record path
	int m, source, dest;
	int ret[MAX_VERTEX_NUM];

	//// user intput part//////////////////
#ifdef DEBUG
	ary = ary_35[0];
	source = 1, dest = 3;
#else
	struct queue res_q;
	int i;
	matrix_num = MAX_VERTEX_NUM;
	scanf("%d", &vernum);
	ary = matrix_input[0];
	get_user_input(ary, vernum, matrix_num);
	scanf("%d", &m);
#endif

	//main code ///////////////////////
	CreateUDN(&testGraph, vernum, matrix_num, ary);
	floyd_shortpath(&testGraph, &ret_dis, &ret_path);

	//print result ////////////////////
#ifdef DEBUG
	m = 2;
	ret[0] = get_floyd_dis(testGraph.vexnum, 1, 3, ret_dis);
	ret[1] = get_floyd_dis(testGraph.vexnum, 4, 1, ret_dis);
	printf("from %d to %d, shortest path is %d", source, dest, source);
	print_floyd_path(ret_path, testGraph.vexnum, 0, 2, NULL, NULL);
	printf("\n");

	printf("from %d to %d, shortest path is %d", 4, 1, 4);
	print_floyd_path(ret_path, testGraph.vexnum, 3, 0, NULL, NULL);
	printf("\n");
#else
	//save path result to queue and ret[]
	initQueue(&res_q, MAX_VERTEX_NUM);

	for (i = 0; i < m; i++) {
		scanf("%d", &source);
		scanf("%d", &dest);
		if (PRINT_LENGTH == type) {
			ret[i] = get_floyd_dis(testGraph.vexnum,
				source + 1, dest + 1, ret_dis);
		} else {//path
			//printf("%d\n", source);
			enQueue(ret, &res_q, source);
			print_floyd_path(ret_path, testGraph.vexnum, source, dest, 
				&res_q, ret);
		}
	}
	printf("\n");
	if (PRINT_LENGTH == type) {
		for (i = 0; i < m; i++) {
			printf("%d\n", ret[i]);
		}
	} else {//path
		while (!queueEmpty(&res_q)) {
			i = deQueue(ret, &res_q);
			printf("%d\n", i);
		}
	}

	destroyQueue(&res_q);
#endif

	//at last, free sources
	floyd_shortpath_free(ret_dis, ret_path);
}

void test_36(void)
{
	test_36_common(PRINT_LENGTH);
}

void test_37(void)
{
	test_36_common(PRINT_PATH);
}

/* test 4-4
 * 输入和4-3完全一样，算法也完全一样
 * 4-3：打印最短路径的长度
 * 4-4：打印出最短路径经过的节点
 * */

int main(int argc, char** argv)
{
	//test_34();
	//test_35();
	//test_36();
	test_37();
	return 0;
}
